package linkedtable;

import org.junit.Test;


/**
 * @Description 25. K 个一组翻转链表 https://leetcode.cn/problems/reverse-nodes-in-k-group/
 * @Author Firenut
 * @Date 2023-02-13 10:07
 */
public class T25_reverseKGroup {
    @Test
    public void test() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;
//        reverseKGroup(node1, 2);
        reverse(node1);

    }

    // 使用哑结点辅助链表的操作,要让每k个结点反转一下,最基本的反转操作是少不了的
    // 要反转链表就需要断开与前面以及后面连接的结点,所以需要保留前后的结点的引用，以方便反转完成之后可以再接上去
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dump = new ListNode();
        dump.next = head;
        ListNode pre = dump, end = dump;
        ListNode next;

        while (end.next != null) {
            for (int i = 0; i < k; i++) {
                if (end == null) {
                    // 如果end还没移动k个位置就到达尾部
                    // 说明最后一段不足以进行反转，直接返回即可
                    break;
                }
                end = end.next;
            }
            if (end == null) {
                return dump.next;
            }
            next = end.next;
            end.next = null;           // 断开与后面结点的连接

            ListNode start = pre.next; // start是反转前链表的头结点,反转后链表的尾结点
            pre.next = reverse(start); // 与前面断开的结点重新连接
            start.next = next;         // 与后面的断开的结点重新连接
            pre = end = start;
        }
        return dump.next;
    }

    // 反转链表 返回的是反转链表的头节点
    ListNode reverse(ListNode head) { // 每一段链表在反转的时候都会断开和前面结点的连接
        ListNode cur, pre, next;
        pre = null;
        cur = head;
        next = cur.next;
        while (next != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = cur.next;
        }
        cur.next = pre;
        return cur;
    }


/*     反转链表 不过这里返回的结点还是head，只不过现在是反转后的尾结点(这样就没法得到反转后的头结点了)
    ListNode reverse(ListNode head){
        if(head.next==null) return head;
        ListNode node = reverse(head.next);
        node.next=head;

        return head;
    }*/
}